package com.tyrone.algorithm.graph;

import com.tyrone.algorithm.linear.Stack;

/**
 * 顶点排序
 */
public class DepthFirstOrder {
    private boolean[] marked;                //索引代表顶点，值表示当前顶点是否已经被搜索
    private Stack<Integer> reversePost;               //使用栈，存储顶点序列

    public DepthFirstOrder(Digraph G){
        reversePost=new Stack<Integer>();
        marked= new boolean[G.V()];
        for (int v = 0; v < G.V(); v++) {
            if (!marked[v]){
                dfs(G, G.V());
            }
        }
    }
    /**
     * 基于深度优先搜索，生成顶点线性序列
     * @param G
     * @param v
     */
   private void dfs(Digraph G,int v){
       marked[v]=true;
       for (Integer w : G.adj(v)) {
           if (!marked[w]){
               dfs(G,w);
           }
       }
       reversePost.push(v);
   }

    /**
     * 获取顶点线性序列
     * @return
     */
   public Stack<Integer> reversePost(){
        return reversePost;
   }

}
